#include <iostream>
#include <stdlib.h>
#include <list>
#include <vector>
#include <stdio.h>
#include <string.h>
#include "grafo.h"


using namespace std;

void execCacm(vector<int> title, vector< vector<int> > v){
	timeval tm1, tm2;
	int nodesCant = title[0];
	int edgesCount = title[1];
	int origen = title[2];
	int destino = title[3];
	int K  = title[4];
	gettimeofday(&tm1, NULL);
	Result* R;
	list<Edge*> S;
	Edge *e = new Edge;
	origen --;
	destino --;
	if (destino<origen) swap(destino,origen);

	Graph *G = new Graph;
	Graph *M = new Graph;
	initGraph(G,nodesCant);
 	initGraph(M,nodesCant);
 	int i =0;

	for (vector< vector<int> >::iterator it = v.begin() ; it != v.end(); ++it){
		e->id  = i;
		e->w1 = (*it)[2];
		e->w2 = (*it)[3];
		putEdge(G,(*it)[0]-1,(*it)[1]-1,e,1);
		i++;
	}

	R = CalcularCamino(G,M,&S,0,origen,K,origen,destino);
	gettimeofday(&tm2, NULL);
	unsigned long long t = 1000 * (tm2.tv_sec - tm1.tv_sec) + (tm2.tv_usec - tm1.tv_usec) / 1000;
	//printf("%ld %lld %s",nodesCant,t, "\n");
	/*if (R != NULL){
		printf("%d %d %d",R->w1,R->w2,R->k);
		for (list<int>::iterator it = R->C.begin() ; it != R->C.end(); ++it){
			printf(" %d",*it+1);
		}
		printf("\n");
	}else{
		printf( "------------\n");
	}*/
}


int main(int argc, char** argv) {

	srand (time(NULL));
	char line[1000];
	vector<int> reader;
	reader.resize(5);
	 char* strVal;
	 int val;
         int readedLine = 0;

	vector <int> instanceTitle (5);
	vector< vector<int> > values;

	 while ( cin.getline(line,50,'\n') && line != "0" ){
		if ((readedLine == 0 &&  0 < instanceTitle.at(4)) ){
			// execCacm(instanceTitle,values);

			execCacm(instanceTitle,values);

			if (line[0] == '0'){
				return 0;
			}

	 	}
	 	if(readedLine == 0){

			strVal = strtok(line," ");
			for (int i =0 ; i< 5; i++){
				val = atoi(strVal);
				instanceTitle[i] = atoi(strVal);
				strVal = strtok(NULL," ");
			}
	 		readedLine = instanceTitle[1];
	 		values.resize(instanceTitle[1]);
	 	}else{

			values[(instanceTitle[1] - readedLine)].resize(4);

			strVal = strtok(line," ");
			for (int i =0 ; i< 4; i++){
				val = atoi(strVal);
				values[(instanceTitle[1] - readedLine)][i] = atoi(strVal);
				strVal = strtok(NULL," ");
			}
			readedLine --;
	 	}
	}

    return 0;
}
